#include <stdio.h>

static void printa(int a[], int n)
{
	for (int i = 0; i < n; i++) {
		printf("%-8d ", a[i]);
		if ((i & 0x7) == 0x7)
			printf("\n");
	}

	printf("\n");
}

static inline void swap_int(int a[], int i, int j)
{
	a[i] = a[i] + a[j];
	a[j] = a[i] - a[j];
	a[i] = a[i] - a[j];
}

void max_heapify(int a[], int n, int i)
{
	int l, r, max;

	l = (i << 1) + 1;
	r = (i << 1) + 2;
	max = i;

	if (l < n && a[l] > a[max])
		max = l;
	if (r < n && a[r] > a[max])
		max = r;
	if (max != i) {
		swap_int(a, max, i);
		max_heapify(a, n, max);
	}
}

void build_max_heap(int a[], int n)
{
	int m = (n / 2) - 1;

	for (int i = m; i >= 0; i--)
		max_heapify(a, n, i);
}

void heap_sort(int a[], int n)
{
	build_max_heap(a, n);
	for (int i = n - 1; i > 0; i--) {
		swap_int(a, 0, i);
		max_heapify(a, i, 0);
	}
}

int main(int argc, char *argv[])
{
	int a[10] = {10, 8, 15, 31, 20, 19, 7, 4, 9, 23};
	
	printa(a, 10);
	heap_sort(a, 10);
	printa(a, 10);

	return 0;
}

